The invention relates to electronic printers, and more particularly to an improved method for representation of an image for raster printing.
Modern computer graphics is based on the frame buffer. The frame buffer provides an internal representation of the image being constructed. Images are displayed as a raster pattern of colored spots or pixels. Frame buffers are blocks of memory partitioned into data entries for each spot on the display, and usually organized according to the raster. The data in the frame buffer element corresponding to a pixel describes the color of that pixel. With the development of the frame buffer and raster graphics came the realization that solid areas (such as polygons) could be described and imaged. But in order to display a polygon, one must convert from the representation in which it is first defined (usually a list of vertex points from which the line segments forming the boundary can be derived) to the format required by the frame buffer (the set of pixels which are enclosed by the polygon). This is called rasterization or scan-conversion, and several approaches have been tried.
One approach (called flood fill or seed fill) is to draw the boundary of the polygon in the frame buffer, using some color other than the background. Then starting at some point known to be within the polygon (the seed), the technique is to grow the region by changing the color of neighboring pixels until the boundary is reached as shown in FIG. 1. This technique can be used to accumulate overlapping polygons, but it may require multiple seeds to access isolated regions. Finding seed points can be difficult and costly.
Another set of algorithms are called parity techniques. If the raster is scanned from left to right, a polygon can be constructed by drawing its left and right boundaries (the leftmost and rightmost points filled regions on each scan line). An area containing the boundary can then be scanned, noting edges as they are crossed. If an odd number of edges are crossed to reach a pixel, then pixel is colored as interior to the polygon. If an even number of edges are crossed, the pixel is outside the polygon and is not colored as illustrated in FIG. 2. This technique does not require seed points, but handling multiple overlapping polygons requires two frame buffers (or one buffer with at least three possible states for each pixel). The technique is to use one buffer to draw the boundary and determine which pixels are interior to a given polygon, and the second frame buffer to actually accumulate the composite image. Note that the first buffer must be cleared between each polygon construction.
A third set of techniques is based on an ordered edge list. It is related to the parity scheme, but does not require the second frame buffer to draw the boundary. Instead, analytic descriptions of the boundary components are stored. The boundary must be represented in a form such that the intersection of the boundary with a scan line is easily calculated. The boundary is usually decomposed into straight-line edge segments, which are sorted into scan line order by their minimum-scan line endpoint. Then for each scan line the intersections with the edges are calculated and sorted into their order within the scan. These points are then used as the boundary for the interior pixels for that scan line. As with parity algorithms, a pixel on the scan line is considered interior if an odd number of boundary points are crossed to reach it as shown in FIG. 3. While this technique does not require the second frame buffer, it is limited to regions with edge descriptions which are monotonic with respect to scan line number, and which can be generated in scan line order. It also entails the processing overhead of decomposing and sorting the polygon's edge segments.
Also included in the prior art is U.S. Pat. No. 4,815,009 to Blatin discloses an algorithm for filling an image outline defined by a plurality of vectors and converting the outline into a set of trapezoids. All areas have a winding number initially set equal to zero. A means of the incrementing and decrementing a counter each time a vector is crossed in a scan line determines the area winding number. Any area with an odd or non-zero winding number, depending on the chosen method of determination, is considered within the outlines and is filled. This technique provides a way of handling objects defined by non-zero winding numbers, but it does so by extensive analysis of the object. It will only work for flat-edged objects, and it must find intersections of edges, sort edges and extract trapezoids. Furthermore, if the trapezoids are filled as suggested, then processing an object requires storing every pixel for its area.
U.S. Pat. No. 4,554,538 to Bieneman discloses a multi-level raster scan display system for overlapping images. A digital memory stores words which are read with a raster scan signal to drive the display screen. An element of an image to be displayed is drawn, moved or erased by selectively incrementing or decrementing the appropriate memory locations. This allows relocation of images without affecting the underlying image content. However, in this system, the object is entered by its area rather than its perimeter requiring the changing of significantly more pixels. Also, this system requires much more storage to supply enough bits at each pixel to count the maximum number of overlapping objects that will occur.
Generally, all of the filling algorithms disclosed in the prior art are based on defining the interior of a polygon by odd winding number. The winding number for a point is the number of times that point is circled in tracing the polygon boundary. Defining a point to be interior if an odd number of boundaries are crossed to reach it is equivalent to defining interior points as having an odd winding number. There is, however, another definition for the interior of a polygon. A point can be defined as interior if it has a non-zero winding number, or a positive winding number can be used as the definition. Page-description languages such as Interpress and PostScript support both non-zero and odd winding number conventions.
The alternative definitions yield different results when a polygon is self-intersecting or several polygons overlap. When the boundaries of two polygons defined by an odd winding number intersect, the parity of the area common to both flips from odd to even, as seen in FIG. 4a. Thus, instead of being filled twice, the common area is not filled at all. This is why parity techniques must rasterize each polygon individually, and need a second frame buffer to accumulate the image.
If a positive winding number is used, overlapping interiors just have greater winding numbers and are still filled as shown in FIG. 4b. Thus, if polygons are defined by positive winding numbers, the boundaries for several of them can be collected and their interiors filled in a single sweep through the scan lines. An adaptation of the ordered-edge-list method to polygons defined by a non-zero winding number involves giving each edge a direction number of -1 or +1, based on whether one moves up or down along the edge as one traces the polygon boundary counter-clockwise. As one steps along a scan line and notes intersections with the boundary, the direction numbers of the edges crossed are added. This total is the winding number for the current point as illustrated in FIG. 5.
It is an object of the present invention, therefore, to provide a new and simple method for rasterizing graphic images. It is another object of the present invention to provide a system wherein the time dependency for rasterization is proportional to the perimeter of the objects drawn rather than their area, and to provide a method that can be supported by hardware and can offer a significant advantage in high-speed image generation. It is another object of the present invention to be capable of rasterizing any shape for which a positive winding number boundary can be drawn. Further advantages of the present invention will become apparent as the following description proceeds and the features characterizing the invention will be pointed out with particularity in the claims annexed to and forming a part of this specification.